package LeetCode.Leet300_399.Leet330_339.Leet337;

/**
 * @ClassName Solution_1
 * @Author 孙天赐
 * @Date 2025/10/23 13:45
 * @Description TODO: 方法一   动态规划    0ms 100%
 */
class Solution_1 {
    public int rob(TreeNode root) {
        int[] result = getMax(root);
        return Math.max(result[0], result[1]);
    }

    // 返回值：[0]表示不偷当前节点的最大值，[1]表示偷当前节点的最大值
    public int[] getMax(TreeNode root) {
        int[] result = new int[2];
        // 节点不存在
        if (root == null) {
            return result;
        }
        // 叶子节点
        if (root.left == null && root.right == null) {
            result[1] = root.val;
            return result;
        }
        int[] left = getMax(root.left);
        int[] right = getMax(root.right);
        // 两种情况
        // 1.偷当前这家，金额为不偷左右孩子的最大值之和，加上当前这家的值
        // 2.不偷当前这家，金额为偷或不偷左右孩子的最大值之和(左右孩子偷不偷都行)
        // 两者取较大者
        result[1] = left[0] + right[0] + root.val;
        result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return result;
    }
}
